#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <istream>
#include <vector>
using ll = int64_t;



int main(){
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n,q;
    std::cin>>n>>q;
    std::vector<ll> lg(n+1);
    for(ll i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
        // printf("lg2[%lld]=%lld\n",i,lg[i]);
    }
    std::vector<std::vector<ll>> bmax(n+1,std::vector<ll>(lg[n]+1)),bmin(n+1,std::vector<ll>(lg[n]+1));
    for(ll i=1;i<=n;i++){
        std::cin>>bmax[i][0];
        bmin[i][0]=bmax[i][0];
    }
    for(ll j=1;j<=lg[n];j++){
        for(ll i=1;i+(1ll<<(j-1))<=n;i++){
            bmax[i][j]=std::max(
                bmax[i][j-1],
                bmax[i+(1ll<<(j-1))][j-1]
            );
            bmin[i][j]=std::min(
                bmin[i][j-1],
                bmin[i+(1ll<<(j-1))][j-1]
            );
        }
    }
    while(q--){
        ll l,r;
        std::cin>>l>>r;
        ll range=r-l+1;
        ll max = std::max(bmax[l][lg[range]],bmax[r-(1ll<<(lg[range]))+1][lg[range]]);
        ll min = std::min(bmin[l][lg[range]],bmin[r-(1ll<<(lg[range]))+1][lg[range]]);
        // printf("max=%lld, min=%lld\n",max,min);
        std::cout<<max-min<<"\n";
    }
}